/**
 * 二叉搜索树（BinarySearchTree）
 * 性质：
 * 1、空树是二叉搜索树；
 * 2、若他的左子树不为空，则左子树上所有的节点值均小于他根节点的值；
 * 3、若他的右子树不为空，则右子树上所有的节点值均大于他根节点的值；
 * 4、他的左右子树均为二叉搜索树。
 */
#include <iostream>

using namespace std;

template <typename T>
struct TreeNode
{
    T val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(T x) : val(x), left(nullptr), right(nullptr) {}
};

template <typename T>
class BinarySearchTree
{
private:
    TreeNode<T> *root; // 根节点

    // 插入
    TreeNode<T> *insertNode(TreeNode<T> *node, T value);
    // 删除
    TreeNode<T> *removeNode(TreeNode<T> *node, T value);
    // 查找
    bool searcheNode(TreeNode<T> *node, T value);
    // 中序遍历
    void inOrder(TreeNode<T> *node);

public:
    BinarySearchTree() : root(nullptr) {}
    ~BinarySearchTree();

    void insert(T value)
    {
        root = insertNode(root, value);
    }

    void remove(T value)
    {
        root = removeNode(root, value);
    }

    bool search(T value)
    {
        return searcheNode(root, value);
    }

    void inOrderTraversal()
    {
        inOrder(root);
        cout << endl;
    }
};

template <typename T>
BinarySearchTree<T>::~BinarySearchTree()
{
    while (root)
    {
        remove(root->val);
    }
}

template <typename T>
TreeNode<T> *BinarySearchTree<T>::insertNode(TreeNode<T> *node, T value)
{
    if (node == nullptr)
    {
        return new TreeNode<T>(value);
    }
    if (node->val < value)
    {
        node->right = insertNode(node->right, value);
    }
    else if (node->val > value)
    {
        node->left = insertNode(node->left, value);
    }
    return node;
}

template <typename T>
TreeNode<T> *BinarySearchTree<T>::removeNode(TreeNode<T> *node, T value)
{
    if (node == nullptr)
    {
        return nullptr;
    }
    // 如果删除的值大于当前的值，找右子树删除
    if (node->val < value)
    {
        node->right = removeNode(node->right, value);
    }
    // 如果删除的值小于当前的值，找左子树删除
    else if (node->val > value)
    {
        node->left = removeNode(node->left, value);
    }
    // 相等的情况***
    else 
    {
        // 如果没有左右子树
        if (node->left == nullptr && node->right == nullptr)
        {
            delete node;
            return nullptr;
        }
        // 没有左子树
        else if (node->left == nullptr)
        {
            TreeNode<T> *rightChild = node->right;
            delete node;
            return rightChild;
        }
        // 没有右子树
        else if (node->right == nullptr)
        {
            TreeNode<T> *leftChild = node->left;
            delete node;
            return leftChild;
        }
        // 左右子树都有（去右侧找一个最小的节点放到此节点即可）
        else
        {
            TreeNode<T> *pTemp = node->right;
            while (pTemp->left)
            {
                pTemp = pTemp->left;   
            }
            node->val = pTemp->val;
            node->right = removeNode(node->right, pTemp->val);
        }
    }
    return node;
}

template <typename T>
bool BinarySearchTree<T>::searcheNode(TreeNode<T> *node, T value)
{
    if (node == nullptr)
    {
        return false;
    }
    if (node->val < value)
    {
        return searcheNode(node->right, value);
    }
    else if (node->val > value)
    {
        return searcheNode(node->left, value);
    }
    return true;
}

template <typename T>
void BinarySearchTree<T>::inOrder(TreeNode<T> *node)
{
    if (node)
    {
        inOrder(node->left);
        cout << node->val << " ";
        inOrder(node->right);
    }
}

int main()
{
    BinarySearchTree<int> bst;
    bst.insert(50);
    bst.insert(30);
    bst.insert(70);
    bst.insert(40);
    bst.insert(80);
    bst.insert(80);
    bst.insert(80);
    bst.insert(60);
    bst.insert(100);

    bst.inOrderTraversal();
    cout << bst.search(100) << endl;
    cout << bst.search(1000) << endl;
    bst.remove(50);
    bst.inOrderTraversal();

    return 0;
}
